// FillStrokeTool.cpp: implementation of the CFillStrokeTool class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "FillStrokeTool.h"
#include <memory.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

int getMaxValue(const short *pn, int nCount);

//////////////////////////////////////////////////////////////////////

const float EPSILON = 1.0e-5f;

//////////////////////////////////////////////////////////////////////
/*
BOOL SLineInfo::isInRect(int x, int y)
{
	ASSERT(this != NULL);
	float df = sqrtf(dx * dx + dy * dy + 0.0f);
	if (m_fMax < EPSILON)
		m_fMax = ((m_ptEnd.x - m_pt0.x) * dx + (m_ptEnd.y - m_pt0.y) * dy) / df;
	float f1 = ((x - m_pt0.x) * dx + (y - m_pt0.y) * dy) / df;
	// not to check head part
	if (f1 < m_fMax / 2)
		return TRUE;
	// to check tail part
	if (f1 > m_fMax+EPSILON)
		return FALSE;
	float f2 = (- (x - m_pt0.x) * dy + (y - m_pt0.y) * dx) / df;
	if (f2 < 0)
		f2 = -f2;
	return (f2 < m_nWeight + EPSILON);
}

BOOL CALLBACK SLineInfo::CheckInRange(void *lpContext, int x, int y)
{
	SLineInfo *pThis = (SLineInfo *)lpContext;
	return pThis->isInRect(x, y);
}//*/

//////////////////////////////////////////////////////////////////////

BOOL SCheckInfo::isInDirection(int x, int y) const
{
	ASSERT(this != NULL);
	float theta = (x - x0) * m_fCosine + (y - y0) * m_fSine;
	// theta >= 0
	return theta > -EPSILON;
}

BOOL CALLBACK SCheckInfo::CheckInRange(void *lpContext, int x, int y)
{
	SCheckInfo *pThis = (SCheckInfo *)lpContext;
	return pThis->isInDirection(x, y);
}

//////////////////////////////////////////////////////////////////////

BOOL SCheckEndInfo::isInCorner(int x, int y)
{
	ASSERT(this != NULL);
	if (!m_nInitData) {
		float f = -m_fSine * m_next_dx + m_fCosine * m_next_dy;
		ASSERT(fabsf(f) > EPSILON);
		m_nInitData = (f>0 ? 1 : -1);
	}
	// testCase: ('飞', 1)
	float f2 = m_next_dx * (x - x0) + m_next_dy * (y - y0);
	if (f2 >= w0)
		return FALSE;
	float f = -m_fSine * (x - x0) + m_fCosine * (y - y0);
	if (m_nInitData < 0)
		f = -f;
	return (f < w0 + EPSILON);
}

BOOL CALLBACK SCheckEndInfo::CheckInRange(void *lpContext, int x, int y)
{
	SCheckEndInfo *pThis = (SCheckEndInfo *)lpContext;
	return pThis->isInCorner(x, y);
}

//////////////////////////////////////////////////////////////////////
#ifdef CIRCLE_FILLER

SEnumFlag::SEnumFlag()
{
	m_pbFlag = NULL;
	m_nMaxX = 0;
	m_nMaxY = 0;
}

SEnumFlag::~SEnumFlag()
{
	destruct();
}

int SEnumFlag::destruct()
{
	ASSERT(this != NULL);
	if (m_pbFlag != NULL) {
		delete[] m_pbFlag;
		m_pbFlag = NULL;
	}
	return 0;
}

BOOL SEnumFlag::createCircle(int nRadius)
{
	ASSERT(this != NULL);
	if (nRadius <= 0)
		return FALSE;
	destruct();
	int n = 2 * nRadius + 1;
	m_nMaxX = n;
	m_nMaxY = n;
	if ((m_pbFlag = new BYTE[n * n]) == NULL)
		return FALSE;
	memset(m_pbFlag, 0, n * n);
	float fDist;
	int x, y, m;
	int nBase = 0;
	for(y=0; y<=nRadius; y++) {
		// left side
		for(x=0; x<=nRadius; x++) {
			fDist = sqrtf((x - nRadius) * (x - nRadius) + (y - nRadius) * (y - nRadius) + 0.0f);
			if (fDist < nRadius + EPSILON) {
				if ((m = 1 + (int)(fDist + 0.5f)) >= 256)
					m = 0xff;
				m_pbFlag[nBase+x] = (BYTE)m;
			}
		}
		// right side
		for(x=nRadius+1; x<m_nMaxX; x++)
			m_pbFlag[nBase+x] = m_pbFlag[nBase+m_nMaxX-x-1];
		nBase += m_nMaxX;
	}
	// bottom side
	for(; y<m_nMaxY; y++)
		memcpy(m_pbFlag+y*m_nMaxX, m_pbFlag+(n-y-1)*m_nMaxX, m_nMaxX);
	return TRUE;
}

BOOL SEnumFlag::enumPoint(LPEnumPoint lpfnEnum, void *lpContext, BOOL fAll) const
{
	ASSERT(this != NULL);
	if (!lpfnEnum || !m_pbFlag)
		return FALSE;
	// to enumerate points, should start from the center point.
	int N = m_nMaxX / 2;
	int nRadius = min(N+1, 255);
	int mInit = (fAll ? 1 : m_nMaxX/2);
	for(int m=mInit; m<=nRadius; m++) {
		int nBase = 0;
		for(int y=0; y<m_nMaxY; y++) {
			for(int x=0; x<m_nMaxX; x++) {
				if (m_pbFlag[nBase+x] != m)
					continue;
				if (!lpfnEnum(lpContext, x-N, y-N))
					return FALSE;
			}
			nBase += m_nMaxX;
		}
	}
	return TRUE;
}

BOOL SEnumFlag::checkFlag(int x, int y) const
{
	ASSERT(this != NULL);
	if (!m_pbFlag)
		return FALSE;
	int N = m_nMaxX / 2;
	int x0 = N + x;
	int y0 = N + y;
	if (x0<0 || y0<0 || x0>=m_nMaxX || y0>=m_nMaxY)
		return FALSE;
	return m_pbFlag[m_nMaxX * y0 + x0] != 0;
}

///////////////////////////////////////////////////////////////////////////////

CCircleFiller::CCircleFiller(CCheckInContour *pCheck)
:CAutoFiller(pCheck)
{
	m_pCheck = pCheck;
	m_pbFlag = NULL;
	m_nFlag = 0;
	m_nRowBytes = 0;
}

CCircleFiller::~CCircleFiller()
{
	m_ptChkList.RemoveAll();
	if (m_pbFlag != NULL) {
		delete[] m_pbFlag;
		m_pbFlag = NULL;
		m_nFlag = 0;
	}
}

BOOL CCircleFiller::resetGetPoint(int x, int y, int nRadius)
{
	ASSERT(this != NULL);
	ASSERT(m_pCheck != NULL);
	// to check arguments
	if (!m_pCheck->inContour(x, y))
		return FALSE;
	// to prepare memory and to clear history
	m_ptChkList.RemoveAll();
	if (!m_pbFlag) {
		int n = (m_pCheck->getMaxX() + 7) / 8;
		int nY = m_pCheck->getMaxY();
		if ((m_pbFlag = new BYTE[n * nY]) == NULL)
			return FALSE;
		m_nFlag = n * nY;
		m_nRowBytes = n;
	}
	memset(m_pbFlag, 0, m_nFlag);
	// to set up candidate list
	SEnumFlag enumFlag;
	m_curPoint.x = (short)x;
	m_curPoint.y = (short)y;
	if (!enumFlag.createCircle(nRadius))
		m_ptChkList.Add(m_curPoint);
	else
		enumFlag.enumPoint(enumCirclePoint, this, TRUE);
	return TRUE;
}

BOOL CCircleFiller::onEnumPoint(int x, int y)
{
	x += m_curPoint.x;
	y += m_curPoint.y;
	if (m_pbFlag[y * m_nRowBytes + (x >> 3)] & (1 << (x & 7)))
		return FALSE;
	// may not in contour
	if (!m_pCheck->inContour(x, y))
		return FALSE;
	m_pbFlag[y * m_nRowBytes + (x >> 3)] |= (1 << (x & 7));
	SPoint pt;
	pt.x = (short)x;
	pt.y = (short)y;
	m_ptChkList.Add(pt);
	return TRUE;
}

BOOL CALLBACK CCircleFiller::enumCirclePoint(void *lpContext, int x, int y)
{
	CCircleFiller *pThis = (CCircleFiller *)lpContext;
	pThis->onEnumPoint(x, y);
	return TRUE;
}
#endif	// CIRCLE_FILLER

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CFillStrokeTool::CFillStrokeTool(CCheckInContour *pCheck)
:m_autoFiller(pCheck, FALSE)
{
	m_pGuide = NULL;
	m_nGuide = 0;
    mStartPt.x = (short)(-1);
    mStartPt.y = (short)(-1);

	m_pbAllFlag = NULL;
	m_nAllFlag = 0;
	m_pbGroup = NULL;
}

CFillStrokeTool::~CFillStrokeTool()
{
	destruct();
}

//////////////////////////////////////////////////////////////////////////

int CFillStrokeTool::setGuides(const SPoint *lpPoint, int nPoint)
{
	ASSERT(this != NULL);
	destruct();
	if (!lpPoint || nPoint<=0)
		return -1;
	m_nGuide = 0;
	m_pGuide = new SPoint[nPoint];
	for(int i=0; i<nPoint; i++) {
		m_pGuide[m_nGuide] = lpPoint[i];
		if (i==0 || m_pGuide[m_nGuide].x!=m_pGuide[m_nGuide-1].x || m_pGuide[m_nGuide].y!=m_pGuide[m_nGuide-1].y)
			m_nGuide++;
	}
	return 0;
}

int CFillStrokeTool::setStartXY(short x, short y)
{
    ASSERT(this != NULL);
    if (x<0 || y<0)
        return -1;
    mStartPt.x = x;
    mStartPt.y = y;
    return 0;
}

//const SPoint POINT_OFFSET[] = {
//    {-1, -1}, {0, -1}, {1, -1},
//    {-1, 0},           {1, 0},
//    {-1, 1},  {0, 1},  {1, 1},
//};
const SPoint POINT_OFFSET[] = {
    {-1, -1}, {0, -1}, {1, -1},
    {-1, 0},           {1, 0},
    {-1, 1},  {0, 1},  {1, 1},
    {-2, -2}, {-1, -2}, {0, -2}, {1, -2}, {2, -2},
    {-2, -1}, {2, -1},
    {-2, 0},  {2, 0},
    {-2, 1},  {2, 1},
    {-2, 2},  {-1, 2}, {0, 2}, {1, 2}, {2, 2},
};
int CFillStrokeTool::getPoints(SPoint **ppPoint)
{
	ASSERT(this != NULL);
	if (ppPoint != NULL)
		*ppPoint = NULL;
	int nSize;
	if ((nSize=m_ptList.GetSize()) <= 0) {
		createPointInList();
        if ((nSize=m_ptList.GetSize()) <= 0) {
            // to create point list by default start point
            if (mStartPt.x<0 || mStartPt.y<0)
                return 0;
            SPoint ptNext;
            CAutoFiller aFiller(m_autoFiller.getChecker(), TRUE);
            if (!aFiller.resetGetPoint(mStartPt.x, mStartPt.y)) {
                // to find a nearest point
                int i, x, y, nMax = sizeof(POINT_OFFSET)/sizeof(POINT_OFFSET[0]);
                for (i=0; i<nMax; i++) {
                    x = mStartPt.x + POINT_OFFSET[i].x;
                    y = mStartPt.y + POINT_OFFSET[i].y;
                    if (aFiller.resetGetPoint(x, y))
                        break;
                }
                if (i == nMax)
                    return 0;
            }
            while (aFiller.getNextPoint(&ptNext, NULL, NULL)) {
                savePoint(ptNext.x, ptNext.y, 0);
                m_ptList.Add(ptNext);
            }
        }
    }
	if ((nSize=m_ptList.GetSize()) <= 0)
		return 0;
	if (!ppPoint)
		return nSize;
	SPoint *p = new SPoint[nSize];
	for(int i=0; i<nSize; i++)
		p[i] = m_ptList[i];
	*ppPoint = p;
	return nSize;
}

int CFillStrokeTool::getGroupCount(int nGroupIdx) const
{
	ASSERT(this != NULL);
	if (nGroupIdx<0 || nGroupIdx+1>=m_nGuide)
		return -1;
	if (!m_pbGroup || m_nMaxX<=0 || m_nMaxY<=0)
		return 0;
	BYTE b = (BYTE)(1 + nGroupIdx);
	int nCount = 0;
	int nMax = m_nMaxX * m_nMaxY;
	for(int i=0; i<nMax; i++) {
		if (m_pbGroup[i] == b)
			nCount++;
	}
	return nCount;
}

int CFillStrokeTool::destruct(void)
{
	ASSERT(this != NULL);
	m_autoFiller.clear();
	m_ptList.RemoveAll();
	if (m_pbAllFlag != NULL) {
		delete[] m_pbAllFlag;
		m_pbAllFlag = NULL;
		m_nAllFlag = 0;
	}
	if (m_pbGroup != NULL) {
		delete[] m_pbGroup;
		m_pbGroup = NULL;
	}
	if (m_pGuide != NULL) {
		delete[] m_pGuide;
		m_pGuide = NULL;
		m_nGuide = 0;
	}
	return 0;
}

/////////////////////////////////////////////////////////////////////

//static double COSINE_30_DEGREE = sqrt(3.0) / 2;
BOOL CFillStrokeTool::createPointInList(void)
{
	SLineInfo *pLine;
	int i, nLine;
#ifdef _WIN32
//	DWORD dwTick1 = GetTickCount();
#endif	// _WIN32
	m_nMaxX = m_autoFiller.getMaxX();
	m_nMaxY = m_autoFiller.getMaxY();
	if ((nLine = createLineInfo(&pLine)) <= 0)
		return FALSE;
	// to set weight of line
	for(i=0; i<nLine; i++) {
		if (!getLineWeight(&pLine[i], i==0, i+1==nLine)) {
			if (i == 0)
				return FALSE;
			pLine[i].m_nWeight = pLine[i-1].m_nWeight;
		}
	}
	// to check very large weight, test case: '阳', 1
/*	for(i=1; i+1<nLine; i++) {
		if (pLine[i].m_nWeight > pLine[i-1].m_nWeight+3 &&
			pLine[i-1].m_nWeight+3 > pLine[i+1].m_nWeight)
			pLine[i].m_nWeight = min(pLine[i-1].m_nWeight+3, pLine[i+1].m_nWeight);
	}//*/
	// to update end point
/*	double df1 = sqrt(pLine[i+0].dx * pLine[i+0].dx + pLine[i+0].dy * pLine[i+0].dy + 0.0);
	for(i=0; i+1<nLine; i++) {
		// only those line will update whose corner angle is above 30 degree
		double df2 = sqrt(pLine[i+1].dx * pLine[i+1].dx + pLine[i+1].dy * pLine[i+1].dy + 0.0);
		double dfCosine = (pLine[i+0].dx * pLine[i+1].dx + pLine[i+0].dy * pLine[i+1].dy) / (df1 * df2);
		if (dfCosine < COSINE_30_DEGREE)
			updateLineEnd(&pLine[i], &pLine[i+1]);
		df1 = df2;
	}//*/
	// to create basic group flags
	if (!m_pbGroup) {
		if ((m_pbGroup=new BYTE[m_nMaxX * m_nMaxY]) == NULL)
			return FALSE;
		memset(m_pbGroup, 0, m_nMaxX * m_nMaxY);
	}//*/
#ifdef _WIN32
//	DWORD dwTick2 = GetTickCount();
#endif	// _WIN32
	// to find point list
	int nMaxLine = nLine;
	for(int n=0; n<nMaxLine; n++)
		appendPointListFromLineInfo(pLine[n], (n+1<nMaxLine ? &pLine[n+1] : NULL), (n+2<nMaxLine ? &pLine[n+2] : NULL), n);
	// to free memory
	delete[] pLine;
#ifdef _WIN32
//	DWORD dwTick3 = GetTickCount();
//	TRACE("cost %d, %d ms\n", dwTick2-dwTick1, dwTick3-dwTick2);
#endif	// _WIN32
	return TRUE;
}
/*
BOOL CFillStrokeTool::updateLineEnd(SLineInfo *pLine, const SLineInfo *pNext)
{
	double df = sqrt(pLine->dx * pLine->dx + pLine->dy * pLine->dy + 0.0);
	float dx = pLine->dx / (float)df;
	float dy = pLine->dy / (float)df;
	int x = pLine->m_ptEnd.x;
	int y = pLine->m_ptEnd.y;
	if (!m_autoFiller.resetGetPoint(x, y))
		return FALSE;
	double df2 = sqrt(pNext->dx * pNext->dx + pNext->dy * pNext->dy + 0.0);
	SCheckEndInfo info;
	info.x0 = x;
	info.y0 = y;
	info.w0 = pLine->m_nWeight;
	info.m_fCosine = dx;
	info.m_fSine = dy;
	info.m_next_dx = pNext->dx / (float)df2;
	info.m_next_dy = pNext->dy / (float)df2;
	info.m_nInitData = 0;
	// to find maximum value, minimum distance
	float fValue = 0;
	float fDist = 0;
	float f1, f2;
	SPoint ptCheck, ptEnd = pLine->m_ptEnd;
	while(m_autoFiller.getNextPoint(&ptCheck, SCheckEndInfo::CheckInRange, &info)) {
		f1 = (ptCheck.x - x) * dx + (ptCheck.y - y) * dy;
		f2 = (ptCheck.x - x) * dy - (ptCheck.y - y) * dx;
		if (f2 < 0)
			f2 = -f2;
		if ((f1 > fValue + EPSILON) || (f1 > fValue - EPSILON) && (f2 < fDist)) {
			ptEnd = ptCheck;
			fValue = f1;
			fDist = f2;
		}
	}
	// to get projecting point
	float fNorm = sqrtf(pLine->dx * pLine->dx + pLine->dy * pLine->dy + 0.0f);
	float fNormalVect[] = {-pLine->dy/fNorm, pLine->dx/fNorm};
	float fAbsValue = (ptEnd.y - pLine->m_ptGuide2.y) * fNormalVect[1] + (ptEnd.x - pLine->m_ptGuide2.x) * fNormalVect[0];
	pLine->m_ptEnd.x = (short)(ptEnd.x - fAbsValue * fNormalVect[0] + 0.5f);
	pLine->m_ptEnd.y = (short)(ptEnd.y - fAbsValue * fNormalVect[1] + 0.5f);
	return TRUE;
}//*/

/// to enumerate point in this line
struct SEnumLinePoint
{
public:
	/// object to save point
	CFillStrokeTool	*pThis;

	// for current line
public:
	BYTE	*m_pbFlag;
	int		m_nMaxX;
	int		m_nRowBytes;
	int		m_nMaxY;

public:
	BOOL inCurrentLine(int x, int y) const;
	static BOOL CALLBACK CheckInCurrentLine(void *lpContext, int x, int y);
};
BOOL SEnumLinePoint::inCurrentLine(int x, int y) const
{
	if (!m_pbFlag || x<0 || x>=m_nMaxX || y<0 || y>=m_nMaxY)
		return FALSE;
	int m = y * m_nRowBytes + (x >> 3);
	if (m_pbFlag[m] & (1 << (x & 7)))
		return FALSE;
	return TRUE;
}

BOOL CALLBACK SEnumLinePoint::CheckInCurrentLine(void *lpContext, int x, int y)
{
	SEnumLinePoint *pThis = (SEnumLinePoint *)lpContext;
	return pThis->inCurrentLine(x, y);
}

BOOL CFillStrokeTool::appendPointListFromLineInfo(const SLineInfo& info, const SLineInfo *pNext, const SLineInfo *pSec, int nPartIndex)
{
	// to fill from start point, exclude points in next line
	SEnumLinePoint elp;
	elp.pThis = this;
	int n = (m_nMaxX + 7) / 8;
	if ((elp.m_pbFlag = new BYTE[n * m_nMaxY]) == NULL)
		return FALSE;
	elp.m_nMaxX = m_nMaxX;
	elp.m_nRowBytes = n;
	elp.m_nMaxY = m_nMaxY;
	// to set flag for last line
	SPoint pt0 = (nPartIndex==0 ? info.m_ptGuide1 : info.m_pt0);
	if (nPartIndex != 0) {
		if (m_nAllFlag <= 0) {
			delete[] elp.m_pbFlag;
			return FALSE;
		}
		ASSERT(n * m_nMaxY == m_nAllFlag);
		memcpy(elp.m_pbFlag, m_pbAllFlag, m_nAllFlag);
		// to enable start filling
		float df = sqrtf(info.dx * info.dx + info.dy * info.dy + 0.0f);
		float dx = info.dx / df;
		float dy = info.dy / df;
		enableStartFilling(elp.m_pbFlag, pt0, dx, dy);
	} else {
		memset(elp.m_pbFlag, 0, n * m_nMaxY);
	}
	// to set flag for next line
	if (pNext != NULL)
		clearFlagForLaterLines(elp.m_pbFlag, info, pNext, pSec);
	// to find a proper start point
	SPoint ptNext;
	if (!m_autoFiller.inContour(pt0.x, pt0.y)) {
		int nMax = max(abs(info.m_ptEnd.x - pt0.x), abs(info.m_ptEnd.y - pt0.y));
		nMax = max(nMax, 2);
		int t = min(2, nMax-1);
		int x = pt0.x + (info.m_ptEnd.x - pt0.x) * t / nMax;
		int y = pt0.y + (info.m_ptEnd.y - pt0.y) * t / nMax;
		if (!m_autoFiller.inContour(x, y)) {
			delete[] elp.m_pbFlag;
			return FALSE;
		}
		pt0.x = (short)x;
		pt0.y = (short)y;
	}
	// to enumerate points
#ifdef CIRCLE_FILLER
	CCircleFiller cf(m_autoFiller.getChecker());
	cf.resetGetPoint(pt0.x, pt0.y, info.m_nWeight);
	while(cf.getNextPoint(&ptNext, SEnumLinePoint::CheckInCurrentLine, &elp))
		savePoint(ptNext.x, ptNext.y, nPartIndex);
#else
	m_autoFiller.resetGetPoint(pt0.x, pt0.y);
	while(m_autoFiller.getNextPoint(&ptNext, SEnumLinePoint::CheckInCurrentLine, &elp))
		savePoint(ptNext.x, ptNext.y, nPartIndex);
#endif	// CIRCLE_FILLER
	// to free memory
	delete[] elp.m_pbFlag;
	// to save these point into list
	savePartPoint(info, nPartIndex);
	return TRUE;
}

BOOL CFillStrokeTool::clearFlagForLaterLines(BYTE *pbFlag, const SLineInfo& info, const SLineInfo *pNext, const SLineInfo *pSec)
{
	float df = sqrtf(info.dx * info.dx + info.dy * info.dy + 0.0f);
	float dx = info.dx / df;
	float dy = info.dy / df;
	// to set flag for next line
	ASSERT(pNext != NULL);
	float df2 = sqrtf(pNext->dx * pNext->dx + pNext->dy * pNext->dy + 0.0f);
	float dx2 = pNext->dx / df2;
	float dy2 = pNext->dy / df2;
	float fCos = dx * dx2 + dy * dy2;
	// to find the concave point
	if (fCos < EPSILON)
		return checkConcavePoint1(pbFlag, info.m_ptGuide2, dx, dy, dx2, dy2);
	BOOL fSkipPart = (fabsf(fCos) >= 0.707f);
	int nSkip = info.m_nWeight + 3;
	// testCase: '阳', 1
	if (fSkipPart || df2<=nSkip) {
		// in 45 degree angle
		float fAngle1 = acosf(dx);
		if (dy < 0)
			fAngle1 = -fAngle1;	// [-PI, PI]
		float fAngle2 = acosf(dx2);
		if (dy2 < 0)
			fAngle2 = -fAngle2;	// [-PI, PI]
		// to get middle angle
		float fHalf = (fAngle1 + fAngle2) / 2;
		float dx0 = cosf(fHalf);
		float dy0 = sinf(fHalf);
		float f0[][2] = {{-dy0, dx0}, {dy0, -dx0}};
		touchPoint(pbFlag, pNext->m_pt0.x, pNext->m_pt0.y, dx2, dy2, f0);
		if (!fSkipPart)
			checkConcavePoint1(pbFlag, info.m_ptGuide2, dx, dy, dx2, dy2);
		else {
			// testCase: '去', 4
			float f2[][2] = {{-dy2, dx2}, {dy2, -dx2}};
			touchPoint(pbFlag, pNext->m_pt0.x, pNext->m_pt0.y, dx2, dy2, f2);
			// testCase: '会', 5
			checkConcavePoint2(pbFlag, info, dx, dy, dx2, dy2);
		}
		// to check short part
		if (fSkipPart && pSec!=NULL && df2<df/2) {
			float df3 = sqrtf(pSec->dx * pSec->dx + pSec->dy * pSec->dy + 0.0f);
			float dx3 = pSec->dx / df3;
			float dy3 = pSec->dy / df3;
			checkConcavePoint3(pbFlag, *pNext, dx2, dy2, dx3, dy3);
		}
	} else {
		float xFrom = pNext->m_pt0.x + dx2 * nSkip;
		float yFrom = pNext->m_pt0.y + dy2 * nSkip;
		float f0[][2] = {{-dy2, dx2}, {dy2, -dx2}};
		touchPoint(pbFlag, xFrom, yFrom, dx2, dy2, f0);
		// testCase: '鞍', 13
		if (!fSkipPart)
			checkConcavePoint1(pbFlag, info.m_ptGuide2, dx, dy, dx2, dy2);
	}
	return TRUE;
}

void CFillStrokeTool::enableStartFilling(BYTE *pbFlag, const SPoint& pt0, float dx, float dy)
{
	int n = (m_nMaxX + 7) / 8;
	int xLast = (int)pt0.x - 10;
	int yLast = -1;
	float x0 = (float)pt0.x;
	float y0 = (float)pt0.y;
	BOOL fInContour = TRUE;
	while(fInContour) {
		int x = (int)(x0 + 0.5f);
		int y = (int)(y0 + 0.5f);
		if (x!=xLast || y!=yLast) {
			if (pbFlag[y * n + (x >> 3)] & (1 << (x & 7)))
				pbFlag[y * n + (x >> 3)] &= ~(1 << (x & 7));
			else
				fInContour = FALSE;
			xLast = x;
			yLast = y;
		}
		x0 += dx;
		y0 += dy;
	}
}

void CFillStrokeTool::touchPoint(BYTE *pbFlag, float xFrom, float yFrom, float dx2, float dy2, float f0[][2])
{
	// testCase: ('马', 2), N=2 is better than N=1
	const int N = 2;
	int n = (m_nMaxX + 7) / 8;
	for(int i=0; i<2; i++) {
		float fx = f0[i][0];
		float fy = f0[i][1];
		if (fabsf(fx)<EPSILON && fabsf(fy)<EPSILON)
			continue;
		// testCase: ('挨', 4)
		int tFrom = (i>0 ? N : 0);
		int tMax = N * 3;
		for(int t=tFrom; t<tMax; t++) {
			float x0 = xFrom + dx2 * t / N;
			float y0 = yFrom + dy2 * t / N;
			int nInContour = 1;
			while(nInContour >= 0) {
				int x = (int)(x0 + 0.5f);
				int y = (int)(y0 + 0.5f);
				if (!m_autoFiller.inContour(x, y))
					nInContour--;
				else if (getAllFlag(x, y))
					NULL;
				else
					pbFlag[y * n + (x >> 3)] |= (1 << (x & 7));
				x0 += fx;
				y0 += fy;
			}
		}
	}
}

int CFillStrokeTool::selectConcavePoint(const SPoint& pt, const SPoint *pPoint, int nPoint, const float fDir1[], const float fDir2[])
{
	int i;
	float f;
	float *pfBuf = new float[nPoint];
	for(i=0; i<nPoint; i++) {
		pfBuf[i] = -1.0f;
		float f1 = fDir1[0] * (pPoint[i].x - pt.x) + fDir1[1] * (pPoint[i].y - pt.y);
		if (f1 < EPSILON)
			continue;
		float f2 = fDir2[0] * (pPoint[i].x - pt.x) + fDir2[1] * (pPoint[i].y - pt.y);
		if (f2 < EPSILON)
			continue;
		f = f1 + f2;
		pfBuf[i] = f;
	}
	// to select local minimum
	float fMin = -1;
	int nBestIndex = -1;
	for(i=0; i<nPoint; i++) {
		if ((f = pfBuf[i]) < -EPSILON)
			continue;
		if (f < pfBuf[(i-1+nPoint)%nPoint]+EPSILON &&
			f < pfBuf[(i+1)%nPoint]+EPSILON) {
			if (fMin<0 || f<fMin-EPSILON) {
				fMin = f;
				nBestIndex = i;
			}
		}
	}
	delete[] pfBuf;
	return nBestIndex;
}

BOOL CFillStrokeTool::checkConcavePoint1(BYTE *pbFlag, const SPoint& pt1, float dx, float dy, float dx2, float dy2)
{
	// to find the normal lines
	float fDiff[] = {dx2 - dx, dy2 - dy};
	float fDir1[] = {-dy, dx};
	float fCheck1 = fDir1[0] * fDiff[0] + fDir1[1] * fDiff[1];
	if (fCheck1 < -EPSILON) {
		fDir1[0] = -fDir1[0];
		fDir1[1] = -fDir1[1];
	}
	float fDir2[] = {-dy2, dx2};
	float fCheck2 = fDir2[0] * fDiff[0] + fDir2[1] * fDiff[1];
	if (fCheck2 < -EPSILON) {
		fDir2[0] = -fDir2[0];
		fDir2[1] = -fDir2[1];
	}
	// to select the concave point
	const SPoint *pPoint;
	int nPoint = m_autoFiller.getChecker()->getContour(&pPoint);
	int nBestIndex = selectConcavePoint(pt1, pPoint, nPoint, fDir1, fDir2);
	// should not fail
	if (nBestIndex < 0)
		return FALSE;
	// to select neighbor points
	int n0 = (nBestIndex - 1 + nPoint) % nPoint;
	int dx_0 = pPoint[n0].x - pPoint[nBestIndex].x;
	int dy_0 = pPoint[n0].y - pPoint[nBestIndex].y;
	float df_0 = sqrtf(dx_0 * dx_0 + dy_0 * dy_0 + EPSILON);
	int n1 = (nBestIndex + 1) % nPoint;
	int dx_1 = pPoint[n1].x - pPoint[nBestIndex].x;
	int dy_1 = pPoint[n1].y - pPoint[nBestIndex].y;
	float df_1 = sqrtf(dx_1 * dx_1 + dy_1 * dy_1 + EPSILON);
	// to find correct direction to the next line segment
	float dxMove, dyMove;
	float fProj0 = (dx_0 * dx + dy_0 * dy) / df_0;
	float fProj1 = (dx_1 * dx + dy_1 * dy) / df_1;
	if (fProj1<0 && fabsf(fProj0)<fabsf(fProj1)) {
		dxMove = dx_0 / df_0;
		dyMove = dy_0 / df_0;
	} else if (fProj0<0 && fabsf(fProj0)>fabsf(fProj1)) {
		dxMove = dx_1 / df_1;
		dyMove = dy_1 / df_1;
	} else
		return FALSE;
	// to set flags for the next line
	float f0[][2] = {{dx, dy}, {-dx, -dy}};
	touchPoint(pbFlag, pPoint[nBestIndex].x, pPoint[nBestIndex].y, dxMove, dyMove, f0);
	return TRUE;
}

BOOL CFillStrokeTool::checkConcavePoint2(BYTE *pbFlag, const SLineInfo& info, float dx, float dy, float dx2, float dy2)
{
	// to find the normal lines
	float fDiff[] = {dx2 - dx, dy2 - dy};
	float fDir1[] = {-dy, dx};
	float fCheck1 = fDir1[0] * fDiff[0] + fDir1[1] * fDiff[1];
	if (fCheck1 < -EPSILON) {
		fDir1[0] = -fDir1[0];
		fDir1[1] = -fDir1[1];
	}
	float fDir2[] = {-dy2, dx2};
	float fCheck2 = fDir2[0] * fDiff[0] + fDir2[1] * fDiff[1];
	if (fCheck2 < -EPSILON) {
		fDir2[0] = -fDir2[0];
		fDir2[1] = -fDir2[1];
	}
	// to select the concave point
	const SPoint *pPoint;
	SPoint pt1 = info.m_ptGuide2;
	int nPoint = m_autoFiller.getChecker()->getContour(&pPoint);
	int nBestIndex = selectConcavePoint(pt1, pPoint, nPoint, fDir1, fDir2);
	// should not fail
	if (nBestIndex < 0)
		return FALSE;
	int nDist = max(abs(pt1.x-pPoint[nBestIndex].x), abs(pt1.y-pPoint[nBestIndex].y));
	if (nDist >= 2 * info.m_nWeight)
		return FALSE;
	// to select neighbor points
	int n0 = (nBestIndex - 1 + nPoint) % nPoint;
	int dx_0 = pPoint[n0].x - pPoint[nBestIndex].x;
	int dy_0 = pPoint[n0].y - pPoint[nBestIndex].y;
	float df_0 = sqrtf(dx_0 * dx_0 + dy_0 * dy_0 + EPSILON);
	int n1 = (nBestIndex + 1) % nPoint;
	int dx_1 = pPoint[n1].x - pPoint[nBestIndex].x;
	int dy_1 = pPoint[n1].y - pPoint[nBestIndex].y;
	float df_1 = sqrtf(dx_1 * dx_1 + dy_1 * dy_1 + EPSILON);
	// to check whether there is a corner or not
	float fCos = (dx_0 * dx_1 + dy_0 * dy_1) / (df_0 * df_1);
	if (fCos < -0.5f)
		return FALSE;
	// to find correct direction to the next line segment
	float dxMove, dyMove;
	float fProj0 = (dx_0 * dx + dy_0 * dy) / df_0;
	float fProj1 = (dx_1 * dx + dy_1 * dy) / df_1;
	if (fProj1<0 && fabsf(fProj0)<-fProj1) {
		dxMove = dx_0 / df_0;
		dyMove = dy_0 / df_0;
	} else if (fProj0<0 && fabsf(fProj1)<-fProj0){
		dxMove = dx_1 / df_1;
		dyMove = dy_1 / df_1;
	} else
		return FALSE;
	// to set flags for the next line
	float fdx = (float)(pPoint[nBestIndex].x - pt1.x);
	float fdy = (float)(pPoint[nBestIndex].y - pt1.y);
	float fdf = sqrtf(fdx * fdx + fdy * fdy + EPSILON);
	fdx /= fdf;
	fdy /= fdf;
	float f0[][2] = {{fdx, fdy}, {-fdx, -fdy}};
	touchPoint(pbFlag, pPoint[nBestIndex].x, pPoint[nBestIndex].y, dxMove, dyMove, f0);
	return TRUE;
}

BOOL CFillStrokeTool::checkConcavePoint3(BYTE *pbFlag, const SLineInfo& info, float dx, float dy, float dx2, float dy2)
{
	// to find the normal lines
	float fDiff[] = {dx2 - dx, dy2 - dy};
	float fDir1[] = {-dy, dx};
	float fCheck1 = fDir1[0] * fDiff[0] + fDir1[1] * fDiff[1];
	if (fCheck1 < -EPSILON) {
		fDir1[0] = -fDir1[0];
		fDir1[1] = -fDir1[1];
	}
	float fDir2[] = {-dy2, dx2};
	float fCheck2 = fDir2[0] * fDiff[0] + fDir2[1] * fDiff[1];
	if (fCheck2 < -EPSILON) {
		fDir2[0] = -fDir2[0];
		fDir2[1] = -fDir2[1];
	}
	// to select the concave point
	const SPoint *pPoint;
	SPoint pt1 = info.m_ptGuide2;
	int nPoint = m_autoFiller.getChecker()->getContour(&pPoint);
	int nBestIndex = selectConcavePoint(pt1, pPoint, nPoint, fDir1, fDir2);
	// should not fail
	if (nBestIndex < 0)
		return FALSE;
	int nDist = max(abs(pt1.x-pPoint[nBestIndex].x), abs(pt1.y-pPoint[nBestIndex].y));
	if (nDist >= 2 * info.m_nWeight)
		return FALSE;
	// to select neighbor points
	int n0 = (nBestIndex - 1 + nPoint) % nPoint;
	int dx_0 = pPoint[n0].x - pPoint[nBestIndex].x;
	int dy_0 = pPoint[n0].y - pPoint[nBestIndex].y;
	float df_0 = sqrtf(dx_0 * dx_0 + dy_0 * dy_0 + EPSILON);
	int n1 = (nBestIndex + 1) % nPoint;
	int dx_1 = pPoint[n1].x - pPoint[nBestIndex].x;
	int dy_1 = pPoint[n1].y - pPoint[nBestIndex].y;
	float df_1 = sqrtf(dx_1 * dx_1 + dy_1 * dy_1 + EPSILON);
	// to check whether there is a corner or not
	float fCos = (dx_0 * dx_1 + dy_0 * dy_1) / (df_0 * df_1);
	if (fCos < -0.5f)
		return FALSE;
	// to find correct direction to the next line segment
	float dxMove, dyMove;
	float fProj0 = (dx_0 * dx + dy_0 * dy) / df_0;
	float fProj1 = (dx_1 * dx + dy_1 * dy) / df_1;
	if (fProj1<0 && fabsf(fProj0)<-fProj1) {
		dxMove = dx_0 / df_0;
		dyMove = dy_0 / df_0;
	} else if (fProj0<0 && fabsf(fProj1)<-fProj0){
		dxMove = dx_1 / df_1;
		dyMove = dy_1 / df_1;
	} else
		return FALSE;
	// to set flags for the next line
	float fdx = (float)(pt1.x - pPoint[nBestIndex].x);
	float fdy = (float)(pt1.y - pPoint[nBestIndex].y);
	float fdf = sqrtf(fdx * fdx + fdy * fdy + EPSILON);
	fdx /= fdf;
	fdy /= fdf;
	float f0[][2] = {{fdx, fdy}, {0, 0}};
	touchPoint(pbFlag, pPoint[nBestIndex].x, pPoint[nBestIndex].y, dxMove, dyMove, f0);
	return TRUE;
}

struct SWeightPoint
{
public:
	short	x;
	short	y;
	int		nLineWeight;
	int		nLineDist;

public:
	static int __cdecl compare(const void *p, const void *q);
};
int __cdecl SWeightPoint::compare(const void *p, const void *q)
{
	const SWeightPoint *p1 = (const SWeightPoint *)p;
	const SWeightPoint *p2 = (const SWeightPoint *)q;
	int m;
	if ((m=p1->nLineWeight-p2->nLineWeight) != 0)
		return m;
	return (p1->nLineDist - p2->nLineDist);
}

BOOL CFillStrokeTool::savePartPoint(const SLineInfo& info, int nPartIndex)
{
	if (!m_pbGroup || nPartIndex<0)
		return FALSE;
	BYTE bFlag = (BYTE)(nPartIndex + 1);
	// to check count
	int i, nCount = 0;
	int nMax = m_nMaxX * m_nMaxY;
	for(i=0; i<nMax; i++) {
		if (m_pbGroup[i] == bFlag)
			nCount++;
	}
	if (nCount <= 0)
		return FALSE;
	// to create weight
	int m, nIndex = 0;
	SWeightPoint *p = new SWeightPoint[nCount];
	for(int y=0; y<m_nMaxY; y++) {
		int nBase = y * m_nMaxX;
		for(int x=0; x<m_nMaxX; x++) {
			if (m_pbGroup[nBase+x] != bFlag)
				continue;
			p[nIndex].x = (short)x;
			p[nIndex].y = (short)y;
			p[nIndex].nLineWeight = (x - info.m_pt0.x) * info.dx + (y - info.m_pt0.y) * info.dy;
			m = -info.dy * (x - info.m_pt0.x) + info.dx * (y - info.m_pt0.y);
			p[nIndex].nLineDist = (m<0 ? -m : m);
			nIndex++;
		}
	}
	ASSERT(nIndex == nCount);
	qsort(p, nCount, sizeof(SWeightPoint), SWeightPoint::compare);
	int nBaseSize = m_ptList.GetSize();
	m_ptList.SetSize(nBaseSize + nCount);
	for(i=0; i<nCount; i++) {
		SPoint pt;
		pt.x = p[i].x;
		pt.y = p[i].y;
		m_ptList.SetAt(nBaseSize+i, pt);
	}
	delete[] p;
	return TRUE;
}

BOOL CFillStrokeTool::savePoint(int x, int y, int nPartIndex)
{
	ASSERT(this != NULL);
	if (getAllFlag(x, y))
		return FALSE;
	setAllFlag(x, y);
	if (m_pbGroup!=NULL && !m_pbGroup[y * m_nMaxX + x])
		m_pbGroup[y * m_nMaxX + x] = (BYTE)(nPartIndex + 1);
	return TRUE;
}

int CFillStrokeTool::createLineInfo(SLineInfo **ppLine)
{
	*ppLine = NULL;
	if (m_nGuide < 2)
		return 0;
	int nLine = m_nGuide - 1;
	SLineInfo *pLine;
	if ((pLine=new SLineInfo[nLine]) == NULL)
		return -1;
	// to get initial value
	for(int i=0; i<nLine; i++) {
		pLine[i].m_ptGuide1 = m_pGuide[i + 0];
		pLine[i].m_ptGuide2 = m_pGuide[i + 1];
		pLine[i].m_pt0 = pLine[i].m_ptGuide1;
		pLine[i].m_ptEnd = pLine[i].m_ptGuide2;
		pLine[i].dx = pLine[i].m_ptGuide2.x - pLine[i].m_ptGuide1.x;
		pLine[i].dy = pLine[i].m_ptGuide2.y - pLine[i].m_ptGuide1.y;
		pLine[i].m_nWeight = 0;
//		pLine[i].m_fMax = 0.0f;
	}
	// to update for index 0
	getLineBeginPoint(&pLine[0]);
	// to update for the final index
	getLineEndPoint(&pLine[nLine-1]);
	// to output
	*ppLine = pLine;
	return nLine;
}

int CFillStrokeTool::createWeightList(short **ppnWeight, const SLineInfo *pLine)
{
	// to clear output
	*ppnWeight = NULL;
	// to create value
	double df = sqrt(pLine->dx * pLine->dx + pLine->dy * pLine->dy + 0.0);
	float dx = pLine->dx / (float)df;
	float dy = pLine->dy / (float)df;
	int nx = pLine->m_ptEnd.x - pLine->m_pt0.x;
	int ny = pLine->m_ptEnd.y - pLine->m_pt0.y;
	int tMax = max(abs(nx), abs(ny));
	short *pnMax = new short[tMax + 1];
	float fnx = nx / (float)tMax;
	float fny = ny / (float)tMax;
	// x_t = x + fnx * t; & y_t = y + fny * t;
	float fx = pLine->m_pt0.x;
	float fy = pLine->m_pt0.y;
	for(int t=0; t<=tMax; t++) {
		pnMax[t] = (short)getPointWeight((int)(fx + 0.5f), (int)(fy + 0.5f), dx, dy);
		fx += fnx;
		fy += fny;
	}
	// to output
	*ppnWeight = pnMax;
	return tMax + 1;
}

const int CAND_ANGLE[][2] = {{1, 0}, {0, 1}, {1, 1}, {-1, -1}};
int CFillStrokeTool::getPointWeight(int x, int y, float fdx, float fdy)
{
	int nWeight[4];
	int nMaxValue = min(m_nMaxX, m_nMaxY) / 4;
	// for the given direction
	int nRes = getPointDirectionWeight(x, y, fdx, fdy, nMaxValue);
	BOOL fPosIn = m_autoFiller.inContour(x, y);
	if (!fPosIn) {
		if (nRes < nMaxValue)
			return nRes;
		return 0;
	}
	int nMax = min(nRes+1, nMaxValue);
	// to choose the minimum value
	for(int i=0; i<4; i++) {
		nWeight[i] = getPointAngleWeight(x, y, CAND_ANGLE[i][0], CAND_ANGLE[i][1], nMax);
		nRes = min(nRes, nWeight[i]);
	}
	return nRes;
}

int CFillStrokeTool::getPointAngleWeight(int x, int y, int dx, int dy, int nMaxValue)
{
	int nRes, nValue[2];
	int dxy[][2] = {{-dy, dx}, {dy, -dx}};
	BOOL fIn = m_autoFiller.inContour(x, y);
	for(int i=0; i<2; i++) {
		int dx0 = dxy[i][0];
		int dy0 = dxy[i][1];
		int tx, ty, nMin = -1;
		BOOL fStatusIn = fIn;
		for(int n=1; nMin<0 && n<nMaxValue; n++) {
			tx = x + dx0 * n;
			ty = y + dy0 * n;
			if (!m_autoFiller.inContour(tx, ty)) {
				if (fStatusIn)
					nMin = n - 1;
			} else {
				fStatusIn = TRUE;
			}
		}
		nValue[i] = (fStatusIn ? nMin : -1);
	}
	if (nValue[0]>=0 || nValue[1]>=0)
		nRes = max(nValue[0], nValue[1]);
	else
		nRes = nMaxValue;
	return nRes;
}

int CFillStrokeTool::getPointDirectionWeight(int x, int y, float dx, float dy, int nMaxValue)
{
	int nRes, nValue[2];
	float dxy[][2] = {{-dy, dx}, {dy, -dx}};
	BOOL fIn = m_autoFiller.inContour(x, y);
	for(int i=0; i<2; i++) {
		float dx0 = dxy[i][0];
		float dy0 = dxy[i][1];
		float tx = (float)x;
		float ty = (float)y;
		int nMin = -1;
		BOOL fStatusIn = fIn;
		for(int n=1; nMin<0 && n<nMaxValue; n++) {
			tx += dx0;
			ty += dy0;
			if (!m_autoFiller.inContour((int)(tx+0.5f), (int)(ty+0.5f))) {
				if (fStatusIn)
					nMin = n - 1;
			} else {
				fStatusIn = TRUE;
			}
		}
		nValue[i] = (fStatusIn ? nMin : -1);
	}
	if (nValue[0]>=0 || nValue[1]>=0)
		nRes = max(nValue[0], nValue[1]);
	else
		nRes = nMaxValue;
	return nRes;
}

BOOL CFillStrokeTool::getLineWeight(SLineInfo *pLine, BOOL fFirst, BOOL fTail)
{
	int nWeight;
	short *pnMax;
	int tMax = createWeightList(&pnMax, pLine);
	// to change select range
	int nMinT = 0;
	int nMaxT = tMax;
	if (!fFirst)
		nMinT = (int)(tMax * 0.2f + 0.5f);
	if (!fTail)
		nMaxT = (int)(tMax * 0.8f + 0.5f);
	// to select from list
	if (nMaxT <= nMinT) {
		nMinT = 0;
		nMaxT = tMax;
	}
	// to check abrupt change
	for(int i=nMinT+1; i<nMaxT; i++) {
		if (pnMax[i-1]>0 && pnMax[i]-pnMax[i-1]>3)
			nMaxT = i;
	}
	///////////////////////////////////////////////
	nWeight = getMaxValue(pnMax+nMinT, nMaxT-nMinT);
	//TRACE("weight=%d\n", nWeight);
	pLine->m_nWeight = nWeight;
	delete[] pnMax;
	return (nWeight > 0);
}

BOOL CFillStrokeTool::getLineBeginPoint(SLineInfo *pLine)
{
	double df = sqrt(pLine->dx * pLine->dx + pLine->dy * pLine->dy + 0.0);
	float dx = pLine->dx / (float)df;
	float dy = pLine->dy / (float)df;
	int x = pLine->m_pt0.x;
	int y = pLine->m_pt0.y;
	if (!m_autoFiller.resetGetPoint(x, y))
		return FALSE;
	SCheckInfo info;
	info.x0 = x;
	info.y0 = y;
	info.m_fCosine = -dx;
	info.m_fSine = -dy;
	// to find minimum value, minimum distance
	float fValue = 0;
	float fDist = 0;
	float f1, f2;
	SPoint ptCheck, pt0 = pLine->m_pt0;
	while(m_autoFiller.getNextPoint(&ptCheck, SCheckInfo::CheckInRange, &info)) {
		f1 = (ptCheck.x - x) * dx + (ptCheck.y - y) * dy;
		f2 = (ptCheck.x - x) * dy - (ptCheck.y - y) * dx;
		if (f2 < 0)
			f2 = -f2;
		if ((f1 < fValue - EPSILON) || ((f1 < fValue + EPSILON) && (f2 < fDist))) {
			pt0 = ptCheck;
			fValue = f1;
			fDist = f2;
		}
	}
	// to get projecting point
	float fNorm = sqrtf(pLine->dx * pLine->dx + pLine->dy * pLine->dy + 0.0f);
	float fNormalVect[] = {-pLine->dy/fNorm, pLine->dx/fNorm};
	float fAbsValue = (pt0.y - pLine->m_ptGuide1.y) * fNormalVect[1] + (pt0.x - pLine->m_ptGuide1.x) * fNormalVect[0];
	pLine->m_pt0.x = (short)(pt0.x - fAbsValue * fNormalVect[0] + 0.5f);
	pLine->m_pt0.y = (short)(pt0.y - fAbsValue * fNormalVect[1] + 0.5f);
	return TRUE;
}

BOOL CFillStrokeTool::getLineEndPoint(SLineInfo *pLine)
{
	double df = sqrt(pLine->dx * pLine->dx + pLine->dy * pLine->dy + 0.0);
	float dx = pLine->dx / (float)df;
	float dy = pLine->dy / (float)df;
	int x = pLine->m_ptEnd.x;
	int y = pLine->m_ptEnd.y;
	if (!m_autoFiller.resetGetPoint(x, y))
		return FALSE;
	SCheckInfo info;
	info.x0 = x;
	info.y0 = y;
	info.m_fCosine = dx;
	info.m_fSine = dy;
	// to find maximum value, minimum distance
	float fValue = 0;
	float fDist = 0;
	float f1, f2;
	SPoint ptCheck, ptEnd = pLine->m_ptEnd;
	while(m_autoFiller.getNextPoint(&ptCheck, SCheckInfo::CheckInRange, &info)) {
		f1 = (ptCheck.x - x) * dx + (ptCheck.y - y) * dy;
		f2 = (ptCheck.x - x) * dy - (ptCheck.y - y) * dx;
		if (f2 < 0)
			f2 = -f2;
		if ((f1 > fValue + EPSILON) || ((f1 > fValue - EPSILON) && (f2 < fDist))) {
			ptEnd = ptCheck;
			fValue = f1;
			fDist = f2;
		}
	}
	// to get projecting point
	float fNorm = sqrtf(pLine->dx * pLine->dx + pLine->dy * pLine->dy + 0.0f);
	float fNormalVect[] = {-pLine->dy/fNorm, pLine->dx/fNorm};
	float fAbsValue = (ptEnd.y - pLine->m_ptGuide2.y) * fNormalVect[1] + (ptEnd.x - pLine->m_ptGuide2.x) * fNormalVect[0];
	pLine->m_ptEnd.x = (short)(ptEnd.x - fAbsValue * fNormalVect[0] + 0.5f);
	pLine->m_ptEnd.y = (short)(ptEnd.y - fAbsValue * fNormalVect[1] + 0.5f);
	return TRUE;
}

///////////////////////////////////////////////////////////////////////////////

BOOL CFillStrokeTool::getAllFlag(int x, int y) const
{
	if (!m_pbAllFlag)
		return FALSE;
	int n = (m_nMaxX + 7) / 8;
	int m = y * n + (x >> 3);
	if (m<0 || m>=m_nAllFlag)
		return FALSE;
	return m_pbAllFlag[m] & (1 << (x & 7));
}

BOOL CFillStrokeTool::setAllFlag(int x, int y)
{
	int n = (m_nMaxX + 7) / 8;
	if (!m_pbAllFlag) {
		if ((m_pbAllFlag = new BYTE[n * m_nMaxY]) == NULL)
			return FALSE;
		int nFlag = n * m_nMaxY;
		memset(m_pbAllFlag, 0, nFlag);
		m_nAllFlag = nFlag;
	}
	int m = y * n + (x >> 3);
	if (m<0 || m>=m_nAllFlag)
		return FALSE;
	m_pbAllFlag[m] |= (1 << (x & 7));
	return TRUE;
}

///////////////////////////////////////////////////////////////////////////////

int getMaxValue(const short *pn, int nCount)
{
	if (!pn || nCount<=0)
		return 0;
	int n, nValue = pn[0];
	for(int i=1; i<nCount; i++) {
		if ((n = pn[i]) > nValue)
			nValue = n;
	}
	return nValue;
}
